Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського»  ЗВІТ до лабораторної роботи № 7 з дисципліни «Програмування складних алгоритмів» Тема «Поняття бінарного дерева. Обхід бінарного дерева. Створення, відображення дерева. Вставлення, видалення елементів у бінарному дереві» Варіант № 11                             Лабораторна робота № 7 Поняття бінарного дерева. Обхід бінарного дерева. Створення, відображення дерева. Вставлення, видалення елементів у бінарному дереві Мета: набути навичок створення та обробки бінарних дерев. Завдання до лабораторної роботи Сформулювати математичну постановку задачі. Обрати метод розв’язання задачі, якщо це необхідно. Розробити графічну схему алгоритму. Записати розроблений алгоритм мовою програмування за варіантом у списку. Представити звіт до роботи. Варіант Обхід дерева Завдання   11  Послідовний 1. Обчислити середнє арифметичне елементів дерева. 2. Вивести на екран ті листи дерева, які мають непарні значення.   Теоретичні відомості Дерева пошуку являють собою структури даних, що підтримують операції пошуку елемента, мінімального і максимального значення, попередника й наступника, вставку і видалення. Основні операції в бінарному дереві пошуку виконуються за час, пропорційний його висоті. Для повного бінарного дерева з n вузлами ці операції виконуються за час O(lg n) у найгіршому випадку. Математичне сподівання висоти побудованого випадковим чином бінарного дерева рівне O(lg n), так що всі основні операції над динамічною множиною в такім дереві виконуються в середньому за час O(lg n). На практиці не завжди можна гарантувати випадковість побудови бінарного дерева пошуку, однак існують версії дерев, у яких гарантується гарний час роботи в найгіршому випадку, а саме — червоно-чорні дерева, висота яких O(lg n). Структура бінарного дерева Бінарне дерево може бути представлене за допомогою зв'язаної структури даних, у якій кожен вузол є об'єктом. На додаток до полів ключа key і супутніх даних, кожен вузол містить поля left, right і p, що вказують на лівий і правий дочірні вузли і на батьківський вузол відповідно. Якщо дочірній чи батьківський вузол відсутні, відповідне поле містить значення NULL. Єдиний вузол, вказівник p якого дорівнює NULL, — це кореневий вузол дерева. Ключі в бінарному дереві пошуку зберігаються таким чином, щоб у будь-який момент задовольняти наступній властивості бінарного дерева пошуку: Якщо x — вузол бінарного дерева пошуку, а вузол y знаходиться в лівому піддереві вузла x, то key [y] ≤ key [x]. Якщо вузол y знаходиться в правому піддереві вузла x, то key [x] ≤ key [y]. / Рисунок 1. Приклад бінарного дерева Властивість бінарного дерева пошуку дозволяє нам вивести всі ключі, що знаходяться в дереві, у відсортованому порядку за допомогою простого рекурсивного алгоритму, названого симетричним обходом дерева (inorder tree walk). Цей алгоритм одержав дану назву в зв'язку з тим, що ключ у корені піддерева виводиться між значеннями ключів лівого і правого піддерева. Існують й інші способи обходу, а саме — обхід у прямому порядку (preorder tree walk), при якому спочатку виводиться корінь, а потом — значення лівого і правого піддерева, і обхід у зворотному порядку (postorder tree walk), коли першими виводяться значення лівого і правого піддерева, а уже потім — кореня. Для обходу дерева потрібен час О(n), оскільки після початкового виклику процедура викликається рівно два рази для кожного вузла дерева: один раз для його лівого дочірнього вузла, і один раз — для правого. Операції вставки і видалення приводять до внесення змін у динамічну множину, що представлена бінарним деревом пошуку. Структура даних повинна бути змінена таким чином, щоб відбивати ці зміни, але при цьому зберегти властивості бінарних дерев пошуку. Результати роботи Створюємо структуру BinTree з полями: дані, ліве та праве піддерево. Функція newBinTree() відповідає за створення дерева. Перевіряємо умову: якщо дерева не існує, ...